package com.cqs.leetcode.string;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author lixiaowen
 * @create 2019-12-16
 */
public class SubstringwithConcatenationofAllWords {

    /**
     *
     * 1. 使用Map 统计words里面的word的词频
     * 2. 要求匹配的串由words的串构成的，中间不能被隔断
     * 3. 因为word是固定的大小，匹配过程中使用大小固定的窗口
     * 4. 若窗口单词没有命中，结束，移动下一个字符，开始匹配
     * 5. 若窗口命中，但是同一个word出现的次数超过words中该字符的次数，相当于被隔断，舍弃
     * 6. words.length各窗口连续命中且没有重复次数超出，添加索引位置
     *
     * @param s
     * @param words
     * @return
     */
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> list = new ArrayList<>();
        if (s == null || words == null || words.length == 0 || s.length() == 0) return list;
        int window = words[0].length();
        Map<String, Integer> map = new HashMap<>();
        for (int j = 0; j < words.length; j++) {
            map.put(words[j], map.getOrDefault(words[j], 0) + 1);
        }
        int totalLen = window * words.length;
        for (int i = 0; i <= (s.length() - totalLen); i++) {
            String unit = s.substring(i, i + window);
            Integer integer = map.get(unit);
            if (integer == null) {
                continue;
            }
            //延迟HashMap的拷贝
            Map<String, Integer> freq = new HashMap<>(map);
            int k = words.length;
            while (--k >= 0 && integer != null && integer > 0) {
                if (k == 0) {
                    list.add(i);
                    break;
                }
                freq.put(unit, integer - 1);
                unit = s.substring(i + k * window, i + (k + 1) * window);
                integer = freq.get(unit);
            }
        }
        return list;
    }

    public static void main(String[] args) {
        SubstringwithConcatenationofAllWords allWords = new SubstringwithConcatenationofAllWords();
        Map<String, String[]> cases = new HashMap<>();
        String key = "barfoobarfoobarman";
        String[] value = {"foo", "bar"};
        cases.put(key, value);
        String key2 = "000000000";
        String[] value2 = {"00", "00"};
        cases.put(key2, value2);
        cases.forEach((k, v) -> {

            List<Integer> substring = allWords.findSubstring(k, v);
            System.out.println(substring);
        });
    }
}
